1. Field
This application relates to methods and apparatuses for traversing a binary tree in a ray tracing system.
2. Description of Related Art
A ray tracing method is a method of producing an image by tracing the path of light incident along a ray toward each of pixels of the image from a viewpoint of a camera. In the ray tracing method, a high-quality image may be produced by reflecting the physical properties (e.g., reflective, refractive, and transmissive properties) of light into a rendering result.
Thus, the ray tracing method has been widely applied to the field of three-dimensional (3D) rendering, e.g., movies or animation, in which scenes are more realistically rendered. The ray tracing method is, however, relatively complicated and slow in calculation, compared to a rasterization method in which an image is produced while projecting a 3D object on a screen, and has thus been considered as a non-real-time rendering method. However, recently, as hardware has been advanced and research has been conducted on a spatial data structure for accelerating an intersection calculation acceleration, a real-time ray tracing method has been introduced.
In ray tracing, a hierarchical acceleration structure is used to detect an adjacent primitive that intersects a ray. Representative examples of spatial acceleration structures that have been widely used include a k-dimensional (k-d) tree, a bounding volume hierarchy (BVH), and a grid.
The k-d tree has been known as a fastest intersection calculation data structure for a static scene. However, since it takes a certain time to build the k-d tree for a scene, a time required to rebuild the k-d tree for a dynamic scene is a heavy burden on performing real-time rendering, unlike for the static scene. To solve this problem, for the past several years, research has been conducted on a BVH, a grid, and other structures that have a relatively low intersection calculation acceleration performance compared to the k-d tree, but can be rapidly built for a dynamic scene.
In ray tracing performance, a large amount of calculation is required to generate a hierarchical acceleration structure by spatially splitting primitives to be rendered, traverse the hierarchical acceleration structure, and conduct an intersection test between a ray and a primitive.
To traverse the hierarchical acceleration structure and conduct the intersection test, stacks are basically required to store information regarding nodes to be processed. If hardware or a graphic processing unit (GPU) is used to process a large number of rays at the same time, the number of stacks should be the same as the number of rays.
However, the use of stacks may be limited by a limited storage space or bandwidth. In this case, a stackless algorithm that does not require a stack may be used to skip a stack operation, or a short stack algorithm using a fixed sized buffer that can replace the stack operation may be used. In these algorithms, when an end node is reached while traversal is performed, the traversal is restarted starting from a root node to traverse another node that has not yet been traversed. In the case of a BVH tree, stackless or short stack traversal is performed using a restart trail method.